home *** CD-ROM | disk | FTP | other *** search
/ Ian & Stuart's Australian Mac: Not for Sale / Another.not.for.sale (Australia).iso / Dr. Doyle / Rivest On Factoring < prev    next >
Text File  |  1994-10-22  |  5KB  |  150 lines
  1.  
  2.  
  3. The article below was taken from:
  4.  
  5.     ftp://rsa.com/pub/ciphertext/vol1n1.txt
  6.  
  7. And is Copyright (C) RSA Data Security Inc.
  8.  
  9. ----------------------------------------------------------------------------
  10.  
  11.  
  12. DR. RON RIVEST ON THE DIFFICULTY OF FACTORING
  13.  
  14. (Since the difficulty of "cracking" the RSA algorithm has long been believed
  15. to be roughly equivalent to the difficulty of factoring a given RSA modulus,
  16. we have decided to reprint one of Ron Rivest's classic papers on the
  17. difficulty of the factoring problem.  -Ed.)
  18.  
  19. Abstract
  20. Here are the results of some simple estimations I have done on the projected
  21. difficulty of factoring various sizes of numbers for the next 25 years.
  22.  
  23. The basic question is:
  24.  
  25. "In the year YYYY, what size number will I be able to factor for an investment
  26. of $DDDD?"
  27.  
  28. To be specific, I've looked at
  29.  
  30. YYYY= 1990, 1995, 2000, 2005, 2010, 2015
  31. and
  32. $DDDD = $25K, $25M, and $25G
  33.  
  34. (that is, $25,000, $25,000,000, and $25,000,000,000). The three levels might
  35. correspond to "individual", "corporate", and "national" levels of attack. All
  36. calculations are done in 1990 dollars.
  37.  
  38. Each of these estimates is also done in an "high," "average," and "low" point
  39. of view. (That is, the high estimates are for the greatest number of digits
  40. possible, while the low estimates are for the least number possible.)
  41.  
  42. The estimates are done in terms of MIP-years, a computational unit of power
  43. analogous to a "kilowatt-hour" of electricity. Specifically, a MIP-year is the
  44. computational power of a one-MIP machine running for one year. A MIP (more
  45. correctly, a MIPS) is a "million-instruction per second" machine. Today's
  46. workstations run in the 1 to 10 MIPS range, and 100 MIPS machines are under
  47. development. One MIP-year corresponds to 3.15x1013 operations.
  48.  
  49. Factoring algorithms
  50. To factor a number n with current technology using the best known algorithms,
  51. we need a number of operations roughly equal to
  52.  
  53. L(n) = exp (_ ln n ln ln n)     (1)
  54.  
  55. (Using, say, the quadratic sieve algorithm.) We use this formula for our "low"
  56. estimates, since this is currently achievable. For our "average" estimate, we
  57. use the formula
  58.  
  59. A(n) = min (L(n), exp (2.08 (ln n)l/3 (ln ln n)2/3))    (2)
  60.  
  61. This presupposes that the number field sieve (NFS) can be generalized to
  62. handle ordinary (cryptographic) numbers, as conjectured in the 1990 ACM STOC
  63. article. Finally, for the high estimates, we use the formula
  64.  
  65. H(n) = exp (1.526 (ln n)l/3 (ln ln n)2/3)       (3)
  66.  
  67. which is the number of operations that NFS now uses for rarefied numbers.
  68. (Achieving this formula would be quite a breakthrough.)
  69.  
  70. Costs of computation
  71. I estimate that today a MIP-year costs about $10, as follows. You can buy
  72. (parts for) a 10-MIP machine for about $500. With a lifetime of five years,
  73. you get 50 MIP-years out of the machine.
  74.  
  75. As for rates of technological progress, for the "low" estimate I assume that
  76. technology only advances at 20%/year. For the "average" estimate I assume that
  77. technology advances at 33%/year, and for the "high" estimate I assume
  78. 45%/year. These are measured in terms of the drop in the cost of a MIP-year in
  79. constant 1990 dollars. Thus, under the high estimate, $10 will buy 1.45 MIP-
  80. years in 1991 and 2.10 MIP-years in 1992, etc.
  81.  
  82. At this rate, we can estimate the number of MIP-years that can be bought for
  83. $1 as follows:
  84.  
  85. Year    Low     Average High
  86. 1990    0.100   0.100   0.100
  87. 1995    0.249   0.416   0.641
  88. 2000    0.619   1.732   4.109
  89. 2005    1.540   7.207   26.340
  90. 2010    3.833   30.000  168.800
  91. 2015    9,540   124.800 1082.000
  92. 2020    23.74   519.500 6935.000
  93.  
  94. Combining this with our "low" ($25K), "average" ($25M), and "high" ($25G)
  95. estimates for dollars available, we arrive at the following chart for the
  96. number of MIP-years affordable. (Here T is the abbreviation for "tera," i.e.
  97. 1012.)
  98.  
  99. Year    Low     Average High
  100. 1990    2.5K    2.5M    2.5G
  101. 1995    6K      10M     16G
  102. 2000    15K     43M     103G
  103. 2005    38K     180M    658G
  104. 2010    96K     750M    4.2T
  105. 2015    239K    3.1G    27T
  106. 2020    549K    13G     173T
  107.  
  108. That is, in the year 2020, a determined opponent with $25G might be able to
  109. afford 173 tera MIP-years to attack a number.
  110.  
  111. Results
  112. We now give the number of operations required to factor numbers of various
  113. sizes under our low, average, and high estimates (formulas (1), (2), and (3)).
  114. These are given in MIP-years.
  115.  
  116. Digits  Low     Average High
  117. 100     74      74      0.1
  118. 150     1M      1M      38
  119. 200     4G      4G      4K
  120. 250     6T      2T      261K
  121. 300     5 x 1015        3 x 1014        10M
  122. 350     2 x 1018        2 x 1016        252M
  123. 400     9 x 1020        1018    5G
  124. 450     2 x 1023        6 x 1019        81G
  125. 500     4 x 1025        2 x 1021        1T
  126.  
  127. Combining the above charts with some additional calculation, we end up with
  128. our low, average, and high estimates for the size of a number (in digits) that
  129. an attacker would be able to factor at various points in time.
  130.  
  131. Year    Low     Average High
  132. 1990    117     155     388
  133. 1995    122     163     421
  134. 2000    127     172     455
  135. 2005    132     181     490
  136. 2010    137     190     528
  137. 2015    142     199     567
  138. 2020    147     204     607
  139.  
  140. Conclusions
  141. If one wishes to devise a "standard" based on a 25-year lifetime for an
  142. average attack, then a recommendation of 200 decimal digits (665 bits) seems
  143. justified. A "super-master" key over the same lifetime might well be chosen to
  144. be three times that length (600 decimal digits, or 1994 bits).
  145.  
  146. - Dr. Ron Rivest
  147.  
  148.  
  149.  
  150.